// var arr = [4,1,6,9,3,2,8,7];

// 左闭右开 区间  双指针
// 位置互换
function update(arr,a,b) { 
  let mid = arr[a]
  arr[a] = arr[b]
  arr[b] = mid
 }
// 
function quickArr(arr,begin,end){
  if(begin >= end - 1)return
  let left = begin;
  let right = end;
  do{
    do left++;while(arr[left] < arr[begin] && left < right) // 从左边依次遍历 判断 是否比 begin这个中轴小
    do right--;while(arr[right] > arr[begin] && left < right)  // 为什么一直那begin来做对比 理解 左闭右开 区间
    if(left<right)update(arr,left,right)
  }while(left < right)
  console.log(left)
  let swapPoint = left == right?right -1 : right // 这是第一次处理 获取其 中间值  4 4的左边集合  右边的 集合再进行一样的处理 直到 begin >= end-1 结束  这边又相对提出一个思想 一定要记住 ，循环处理 什么时候 结束 什么情况 终结 而不是无脑写 然后再去改，调试 结束情况
  console.log(swapPoint)
  update(arr, begin, swapPoint);
  quickArr(arr, begin, swapPoint);
  quickArr(arr, swapPoint + 1, end);
}
function normalQuickSort(arr) {
  if(arr == null && arr.length == 0)return [];

  quickArr(arr,0,arr.length)
}
// normalQuickSort(arr)
// console.log(arr)

// 多层次拆分理解 标准快速排序 ，个人理解 应用到二指针 二指针来左右两个指针向中间收缩， 递归循环操作

var a = [2, 6, 7, 8, 3, 9, 1, 4]//[1, 2, 7, 8, 3, 9, 6, 4]

function reQuickSort(arr,begin,end) {
  console.log('初始值',a,begin,end)
      if(begin >= end)return;
       
      let left = begin; 
      let right = end;  
      do{
        do left++;while(left < right && arr[left] < arr[begin])
        do right--;while(left < right && arr[right] > arr[begin])
        if(left<right)exchange(arr,left,right)

      }while(left < right)
      console.log(a)

      //第一次循环处理 [2, 1, 7, 8, 3, 9, 6, 4]
      //对比下 区别1 6 换了位置
      // 比2小[1] 比2 大的[ 7, 8, 3, 9, 6, 4]
      // 第二次循环
      // 基于 if(left == right)
      let midIndex = 0; // 作为 最终跟begin 进行 提换位置 也可以这么理解 获取最小值的 index
      if(left == right){
          midIndex = right -1
      }else if(right < left){
        midIndex = right
      }
      console.log(midIndex) // 1
      // 在上面循环中止的条件就是left >= right的情况
      //为了更清晰的看 我们重新写一个这个方法copy下
      // midIndex 怎么的过来的呢 
      //left 是只要 比begin 小 left ++ 这样left最后的值一定 <= begin的值 为什么呢这就是do while 的在不满足条件的情况下 在检查while()条件是否为真之前，该循环首先会执行一次do{}之内的语句 left++ 那上一次的left 在a[left]>=在a[begin]的值 
      // right 是只要比 begin 大 right-- 在a[right] >= a[begin]  right继续--
      //  这时候会 发现 left 和 right 仍然满足 left < right 情况 说明可能 他们左右往中间进行 收缩的时候
      // 都遇到条件终止 这时候 left - right 之间的值不是就无法遍历到 这时候 我们需要把当前这次外循环 a[left]>a[begin] right<a[begin] 为什么不带等于号，等于等于号的时候left 和right 一定 left >= right  了
      // 我们把left 和 right 的位置 值 进行替换
     
      exchange(arr,begin,midIndex) // 先把位置替换
       // 然后进入 下一次循环
         // exchange(arr,begin,midIndex)// 0 ,1 为什么要换位呢 因为 midIndex 一定是 begin小 放在左边区间 如果我们把数组改成[1, 2, 7, 8, 3, 9, 6, 4]
      //看看会怎么样 midIndex == 0    0 和 0互换不影响 最终midIndex >= begin
      // console.log(a)
      // 这边我们把begin 和 midIndex进行 再换位下 [1, 2, 7, 8, 3, 9, 6, 4]
      // 这时候我们把begin midindex 区间左范围继续 相同的循环处理
      // 我们就叫 reQuickSortleft

      reQuickSortleft(arr,begin,midIndex)
      reQuickSortRight(arr,midIndex+1,end)
      // console.log(a)

    
      

      // console.log(a)
      
 }
 function reQuickSortleft(arr,begin,end) {
  console.log('第二次循环初始值',a,begin,end) // [2, 1, 7, 8, 3, 9, 6, 4] 0 1
  if(begin >= end){
      
      return
  } ;
  let left = begin; // 0
  let right = end; // 1
  do{
    do left++;while(left < right && arr[left] < arr[begin]) // a[1] > a[0] => left = 1
    do right--;while(left < right && arr[right] > arr[begin]) // a[1] > a[0] => right = 0
    if(left<right)exchange(arr,left,right)

  }while(left < right)
  // console.log(a)


  let midIndex = 0; 
  if(left == right){
      midIndex = right -1
  }else if(right < left){
    midIndex = right
  }
  exchange(arr,begin,midIndex) // 先把位置替换
  reQuickSortleft(arr,begin,midIndex)
  reQuickSortRight(arr,midIndex+1,end)
  // reQuickSortleft2(arr,begin,midIndex)
  // exchange(arr,begin,midIndex)
  console.log(arr)
  
}
function reQuickSortRight(arr,begin,end) {
  console.log('第三次循环初始值',a,begin,end) // 
  if(begin >= end){
      
      return
  } ;
  let left = begin; // 0
  let right = end; // 1
  do{
    do left++;while(left < right && arr[left] < arr[begin]) // a[3] > a[2] => left = 3
    do right--;while(left < right && arr[right] > arr[begin]) // a[7](4) > a[2](7) => right = 7
    if(left<right)exchange(arr,left,right) // 这是后 7 和 3值互换位置
    console.log('right 互换位置', arr)
  }while(left < right)
  // 中轴 7 左 4，3 6 右 9 8
  console.log(a)


  let midIndex = 0; 
  if(left == right){
      midIndex = right -1
  }else if(right < left){
    midIndex = right
  }
  exchange(arr,begin,midIndex) // 先把位置替换
  reQuickSortleft(arr,begin,midIndex)
  reQuickSortRight(arr,midIndex+1,end)
  // reQuickSortleft(arr,begin,midIndex)
  // exchange(arr,begin,midIndex)
  console.log(arr)
  
}
 function exchange(arr,i,j) { 
      let mid = arr[i]
     
      arr[i] = arr[j]
      arr[j] = mid
  }
  reQuickSort(a,0,a.length)
  


  // 最后我们手速快的写一次

  // var test = [ 9, 8 ,7 ,6 ,5 ,4,2,1]
  var test = [ 1,3,2]
// 循环处理 拆分出 左右范围
  function testSort ( arr,begin,end){
    if(begin >= end) return
    let left = begin
    let right = end
    do{
        do left++;while(left<right && arr[left] < arr[begin]) 
        do right--;while(left<right && arr[right] > arr[begin])
        if(left < right)changeAB(arr,left,right)
    }while(left < right)
    let mid;
    if(left > right){
      mid = right
    }else{
      mid = right - 1
    }
    console.log('中间bg情况',begin,end)
    console.log('中间情况',left,right,mid)
    changeAB(arr,begin,mid)
    testSort(arr,begin,mid)
    testSort(arr,mid+1,end)
  }
  // 替换位置
  function changeAB(arr,a,b){
     if(arr == null || arr.length == 0)return
      const mid = arr[a]
      arr[a] =arr[b]
      arr[b] =  mid
  }

  testSort(test,0,test.length)
  console.log('最终手写',test)